package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import com.gitee.feizns.explore.data_structure.array_and_string.rotate.Rotate;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author feizns
 * @since 2020/3/9
 */
public class PathSum {

    public static void main(String[] args) {
//        new PathSum().pathSum()
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        return dfs(root, sum);
    }

    private List<List<Integer>> dfs(TreeNode curt, int sum) {
        List<List<Integer>> ret = new ArrayList<>();
        if ( curt != null ) {
            if ( curt.val == sum && curt.left == null && curt.right == null )
                ret.add(new LinkedList<>(Arrays.asList(curt.val)));
            else {
                List<List<Integer>> w = dfs(curt.left, sum - curt.val);
                List<List<Integer>> q = dfs(curt.right, sum - curt.val);
                w.stream().forEach(i -> { i.add(0, curt.val); ret.add(i); });
                q.stream().forEach(i -> { i.add(0, curt.val); ret.add(i); });
            }
        }
        return ret;
    }

}
